home *** CD-ROM | disk | FTP | other *** search
- Path: news.bs.tpl.net!news
- From: Dieter Lⁿcking <luecking@braunschweig.netsurf.de>
- Newsgroups: comp.lang.c++
- Subject: algorithm
- Date: Tue, 02 Apr 1996 06:51:29 +0100
- Organization: IRD Daten- und Netzwerktechnik
- Message-ID: <3160C061.6A7@braunschweig.netsurf.de>
- NNTP-Posting-Host: plueckin.braunschweig.netsurf.de
- Mime-Version: 1.0
- Content-Type: text/plain; charset=us-ascii
- Content-Transfer-Encoding: 7bit
- X-Mailer: Mozilla 2.0 (Win95; I)
-
- An algorithm:
-
- // ============================================================================================
- // Contents:
- // ============================================================================================
- //
- // xtExchange
- //
- // ============================================================================================
- // (Created) Dieter Luecking
- // ============================================================================================
-
- #include <assert.h>
-
-
- // ============================================================================================
- // xtEchange
- // ============================================================================================
- //
- // Arguments: 'TYPE* start' is the stating position.
- // 'const TYPE* mark' is the marked position (condition: 'start' <= 'mark').
- // 'const TYPE* end' is the ending positin (condition: 'mark' <= 'end').
- // Description: This function exchanges all values in front of 'mark' with all values
- // at and after 'mark' upto 'end'.
- // Return: A pointer to the new position of of 'start'.
- // Example: Array: "start XXX mark YYY end ZZZ"
- // Exchanged: "mark YYY start XXX end ZZZ"
- // Remarks: The execution time is (in the worst case) linear to 'end' - 'start'.
- // However 'TYPE::opertor == (const T&)' is invoked twice and may reduce
- // the performance.
- //
- // ============================================================================================
-
- template <class TYPE>
- TYPE* xtExchange(TYPE* start, const TYPE* mark, const TYPE* end) {
- assert(start <= end && star <= mark && mark <= end);
- TYPE* p = start;
- TYPE* newpos = p + (end - mark);
- TYPE* s = (TYPE*)mark;
- TYPE t;
- while(mark < end) {
- while(p < mark && s < end) {
- t = *s;
- *p++ = *s;
- *s++ = t;
- }
- if(p == mark) mark = s;
- else s = (TYPE*)mark;
- }
- return newpos;
- }
-
- template <class T>
- inline TYPE* xtExchange(TYPE* start, const TYPE* mark, size_t size) {
- return xtExchange(start, mark, start + size; }
-
- template <class T>
- inline TYPE* xtExchange(TYPE* start, size_t mark, size_t size) {
- return xtExchange(start, start + mark, start + size); }
-
-
- // ============================================================================================
- // EOF
- // ============================================================================================
-
- I hope that more discussions refer to programming.
- Have a nice work
- Dieter Luecking
-
- P.S.:
- Respose to luecking@braunschweig.netsurf.de
-
-